package LinkedList;

/**
 * 题目 ：回文链表
 *
 * 给定一个链表的 头节点 head ，请判断其是否为回文链表。
 * 如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
 */
public class OfferP27 {
    public boolean isPalindrome(ListNode head) {
        // 考虑极端情况 ：若是链表长度为空或是1的话，即其必然不为回文链表；
        if(head == null || head.next == null){
            return true;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        // 标志位，用来记录初始链表的节点数为奇数还是偶数
        Boolean flag = true;
        ListNode prev = null;
        while(fast.next != null){
            // 若是只是执行了一次fast = fast.next，即，代表初始链表节点数为奇数
            flag = false;
            prev = slow;
            fast = fast.next;
            slow = slow.next;
            if(fast.next != null){
                flag = true;
                fast = fast.next;
            }
        }
        ListNode afterList = slow.next;
        /**
         *  若是初始链表的节点数为偶数的话，即不需要忽略中心节点（由于中心节点有两个，为保证两条链表的长度一致）；
         *  同时，若是初始链表的节点数为奇数的话，即需要去忽略中心节点（由于其中心节点只有一个，需要去保证两条链表的长度一致）
         */
        if(flag){
            slow.next = null;
        }
        else {
            prev.next = null;
        }

        ListNode node = reverseList(afterList);
        // 此处截断所获得两条链表必然长度是一致的
        return compareTwoList(head,node);
    }

    private boolean compareTwoList(ListNode head, ListNode node) {
        while(head != null && node != null){
            if(head.val != node.val){
                break;
            }
            head = head.next;
            node = node.next;
        }
        if(head == null){
            return true;
        }
        return false;
    }
    // 反转链表
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode now = head;
        while(now != null){
            ListNode next = now.next;
            now.next = prev;
            prev = now;
            now = next;
        }
        return prev;
    }
}
